package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description
 * 复杂链表的复制
 * <p>
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
 * 请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。
 *
 * 输入：
 * {1,2,3,4,5,3,5,#,2,#}
 * 返回值：
 * {1,2,3,4,5,3,5,#,2,#}
 * @date 2021/11/8 8:02
 **/
public class RandomListNodeClone {

    public static void main(String[] args) {
        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);
        RandomListNode node5 = new RandomListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        node1.random = node3;
        node2.random = node5;
        node4.random = node2;

    }


    static RandomListNode clone(RandomListNode pHead) {
        if (null == pHead) {
            return null;
        }
        RandomListNode cur = pHead;
        // 1.复制链表 A->B->C 变成 A->A'->B->B'->C->C'
        while (cur != null) {
            RandomListNode node = new RandomListNode(cur.label);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }

        // 2.复制随机的链表
        cur = pHead;
        RandomListNode clone = cur.next;
        RandomListNode res = pHead.next;
        while (null != cur) {
            clone.random = cur.random == null ? null : cur.random.next;
            if (cur.next != null) {
                cur = cur.next.next;
            }
            if (clone.next != null) {
                clone =  clone.next.next;
            }
//            if (cur.random != null) {
//                cur.next.random = cur.random.next;
//            }
//            cur = cur.next.next;
        }

        // 3.拆分链表
        cur = pHead;
        clone = pHead.next;

        while (cur != null && clone != null) {
            if (cur.next != null) {
                cur.next = cur.next.next;
            }
            if (clone.next != null) {
                clone.next = clone.next.next;
            }

            cur = cur.next;
            clone = clone.next;
        }

        return res;
    }

}
